<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /*
            思路：字符串匹配问题，一定是动态规划，定义二维dp数组
            ①初始化dp数组  dp[i][j]表示长度为i的字符串s可以匹配长度为j的字符串p
            ②状态转移方程：
                如果s[i-1]==p[j-1]即尾序列相同或者p[j-1]=='.'，那么只需要比较前面的即dp[i][j]=dp[i-1][j-1]
                如果尾序列不同，需要判断p[j-1]是否为'*',因为*可以重复p[j-2]0次，1次，多次
                因此，需要继续比较s[i-1]和p[j-2]
             s[i-1]==p[j-2]||p[j-2]=='.',这种情况下，*号可以让p[j-3]重复0次，1次，多次

                2.2 让其出现0次，如果字符串p更多，即s='ab'  p='abbb*',需要删除p中字符,那么只需要继续比较长度为i的字符串s和长度为j-2的字符串p
                dp[i][j]=dp[i][j-2]
                2.3如果字符串s更多，即s='aabbb' p='ab*'，需要重复多次，那么其实等同于删除s多次
                dp[i][j]=dp[i-1][j]
                这三种有一种情况满足即可
                 2.4如果s[i-1]!=p[j-2]，那么只需要删除p[j-2]继续比较s[i-1]和p[j-3]
                即dp[i][j]=dp[i][j-2]

            */
            var isMatch = function (s, p) {
                let dp = new Array(s.length + 1).fill().map(() => new Array(p.length + 1).fill(false))
                dp[0][0] = true
                //如果字符串s为空，p后面是*
                for (let j = 1; j <= p.length; j++) {
                    if (p[j - 1] == "*") {
                        dp[0][j] = dp[0][j - 2]
                    }
                }

                for (let i = 1; i <= s.length; i++) {
                    for (let j = 1; j <= p.length; j++) {
                        if (s[i - 1] == p[j - 1] || p[j - 1] == ".") {
                            dp[i][j] = dp[i - 1][j - 1]
                        } else if (p[j - 1] == "*") {
                            if (s[i - 1] == p[j - 2] || p[j - 2] == ".") {
                                dp[i][j] = dp[i][j - 2] || dp[i - 1][j]
                            } else {
                                dp[i][j] = dp[i][j - 2]
                            }
                        }
                    }
                }
                return dp[s.length][p.length]
            }
            isMatch("aab", "ab")
        </script>
    </body>
</html>
